<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-22 09:58:26
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-24 14:43:19
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>路径总和</title>
</head>

<body>
    <script>
        // 求路径和
        // 递归法
        // 1、确定返回值和参数
        // 这道题我们要遍历从根节点到叶子节点的的路径看看总和是不是目标和。
        // 递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
        // 搜索一整颗二叉树不需要返回值，
        // 搜索二叉树且需要处理递归返回值，就需要返回值
        // 搜索其中一条路径就需要返回值

        // 2、终止条件
        // 方案1、和每次减去二叉树节点值，如果值恰好为0而且是叶子节点就是了。否则就不是

        // 方案2累加求每个节点和如果正好是给定值而且是叶子节点就是了

        // 3、确定单次递归逻辑
        // 不让为空的节点进入递归，
        //递归函数的返回值，如果返回true立即终止，退出递归并返回

        let hasPathSum = (root, targetSum) => {
            //递归
            let traversal = (node, cnt) => {
                //遇到子节点且cnt为0，
                if (cnt === 0 && !node.left && node.right) {
                    return true
                }
                if (!node.left && !node.right) {
                    return false;
                }
                //左侧空节点遍历返回true
                if (node.left && traversal(node.left, ctn - node.left.val)) {
                    return true;
                }

                //右侧空节点遍历返回true
                if (node.right && traversal(node.right, ctn - node.right.val)) {
                    return true;
                }
                return false;
            }
            return traversal(root, targetSum - root.val);
        }


        //迭代
        var hasPathSum = function (root, targetSum) {

            if (root === null) {
                return false;
            }
            let nodeArr = [root];
            let valArr = [0];
            while (nodeArr.length) {
                let curNode = nodeArr.shit();
                let curVal = valArr.shift();
                curVal += curNode.val;
                // 为叶子节点，且目标等于和，返回true
                if (curNode.left === null && curNode.right === null && curVal === targetSum) {
                    return true;
                }

                if (curNode.left) {
                    nodeArr.push(curNode.left);
                    valArr.push(curVal);
                }

                if (curNode.right) {
                    nodeArr.push(curNode.right);
                    valArr.push(curVal);
                }


            }

            return false;
        }

        // 路径和2：
        // 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
        // 说明: 叶子节点是指没有子节点的节点。
        // 方法1：递归
        var hasPathSum = function (root, targetSum) {
            const traversal = (node, cnt) => {
                if (cnt === 0 && !node.left && !node.right) {
                    return true;
                }
                if (!node.left && !node.right) {
                    return false;
                }
                if (node.left && traversal(node.left, cnt - node.left.val)) {
                    return true;
                }
                if (node.right && traversal(node.right, cnt - node.right.val)) {
                    return true;
                }
                return false;
            }
            if (!root) {
                return false;
            }

            return traversal(root, targetSum - root.val)

        }
        // 遍历
        let hasPathSum = function (root, targetSum) {
            if (root === null) {
                return false;
            }
            let nodeArr = [root];
            let valArr = [0];
            while (nodeArr.length) {
                let curNode = nodeArr.shift();
                let curVal = valArr.shift();
                curVal += curNode.val;
                if (curNode.left === null && curNode.right === null && curVal === targetSum) {
                    return false;
                }
                if (curNode.left) {
                    nodeArr.push(curNode.left);
                    valArr.push(curVal);
                }
                if (curNode.right) {
                    nodeArr.push(curNode.left);
                    valArr.push(curVal);
                }
            }

            return false;
        }


        //迭代==========
        let pathSum = function (root, targetSum) {
            if (root === null) {
                return [];
            }
            let nodeArr = [root];
            let resArr = [];
            let tempArr = [];
            let countArr = [0];
            while (nodeArr.length) {
                let curNode = nodeArr.shift();
                let curVal = countArr.shift();
                let curNodeArr = tempArr.shift();
                curVal += curNode.val;
                curNodeArr.push(curNode.val);
                if (curNode.left === null && curNode.right === null && curVal === targetSum) {
                    resArr.push(curNodeArr);
                }
                if (curNode.left) {
                    nodeArr.push(curNode.left);
                    countArr.push(curVal);
                    tempArr.push([...curNodeArr]);
                }
                if (curNode.right) {
                    nodeArr.push(curNode.right);
                    countArr.push(curVal);
                    tempArr.push([...curNodeArr]);
                }
            }

            return resArr;
        }

    </script>
</body>

</html>